package com.fallsvc.re.javasesets.ebtree;

import java.util.Scanner;
import java.util.Stack;

class TreeNode{
    char val;
    TreeNode left;
    TreeNode right;
    public TreeNode(char ch) {
        this.val = ch;
    }
}

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            TreeNode root = createTree(str);
            inOrderPrint(root);
        }
    }

    public static int i = 0;


    // 前序数组 创建树
    public static TreeNode createTree(String str) {
        TreeNode root = null;
        if (i == str.length()) return root;

        char ch = str.charAt(i);
        if (ch != '#') {
            root = new TreeNode(ch);
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        } else {
            i++;
        }
        return root;
    }

    // 中序遍历二叉树
    public static void inOrderPrint(TreeNode root) {
        if (root == null) return;
        inOrderPrint(root.left);
        System.out.printf(root.val + " ");
        inOrderPrint(root.right);
    }
    // 二叉树的公共节点
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(p == root || q == root) return root;

        TreeNode leftFind = lowestCommonAncestor(root.left,p,q);
        TreeNode rightFind = lowestCommonAncestor(root.right,p,q);
        if(leftFind != null && rightFind != null) {
            return root;
        }else if (leftFind != null) {
            return leftFind;
        }else{
            return rightFind;
        }
    }
    // Stack + 递归
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q){
        if(root==null) return null;

        Stack<TreeNode> stack1=new Stack<>();
        Stack<TreeNode> stack2=new Stack<>();
        getPath(root,p,stack1);
        getPath(root,q,stack2);

        int size1=stack1.size();
        int size2=stack2.size();

        if(size1>size2){
            int n=size1-size2;
            while(n-->0) {
                stack1.pop();
            }
        }else{
            int n=size2-size1;
            while (n-->0){
                stack2.pop();
            }
        }
        while(!stack1.isEmpty()){
            TreeNode node=stack1.pop();
            if(node==stack2.pop()){
                return node;
            }
        }

        return null;
    }
    // 递归
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if(root == null) return false;
        stack.push(root);
        if(root == node) return true;

        boolean ret = getPath(root.left,node,stack);
        if(ret){
            return true;
        }
        ret = getPath(root.right,node,stack);
        if(ret){
            return true;
        }

        stack.pop();
        return false;
    }
}